# source: https://leetcode.cn/problems/design-an-atm-machine/ 贪心 设计
import bisect
class ATM:

    def __init__(self):
        self.money = [20, 50, 100, 200, 500]
        self.store = [0 for _ in range(5)]

    def deposit(self, banknotesCount: List[int]) -> None:
        for i, v in enumerate(banknotesCount):
            self.store[i] += v

    def withdraw(self, amount: int) -> List[int]:
        cnt = [0 for _ in range(5)]
        ticket = -1
        self.temp = self.store.copy()
        while amount > 0:
            ind = bisect.bisect_right(self.money, amount) - 1
            while ind >= 0:
                ticket = amount // self.money[ind]
                if self.temp[ind] > 0:
                    break
                ind -= 1
            else:
                return [-1]
            
            cnt[ind] += min(ticket, self.store[ind])
            self.temp[ind] -= cnt[ind]
            amount -= min(ticket, self.store[ind]) * self.money[ind]

        self.store = self.temp.copy()
        return cnt


# Your ATM object will be instantiated and called as such:
# obj = ATM()
# obj.deposit(banknotesCount)
# param_2 = obj.withdraw(amount)

# source:https://leetcode.cn/problems/find-the-longest-equal-subarray/submissions/591230619/ 滑动窗口 二刷 一刷 8.14
class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        ans = 0
        count = defaultdict(list)
        d = defaultdict(list)
        last = defaultdict(int)
        i = 0
        while i < len(nums):
            cnt = 1
            if count[nums[i]]:
                d[nums[i]].append(i-1-last[nums[i]])
            while i < len(nums)-1 and nums[i] == nums[i+1]:
                i += 1
                cnt += 1
            last[nums[i]] = i
            count[nums[i]].append(cnt)
            i += 1
        # print(d)
        # print(count)
        for key in count.keys():
            if not d[key]:
                d[key].append(0)

        for key in d.keys():
            temp, left = 0, 0
            total = count[key][left]
            ans = max(ans, total)
            for right, v in enumerate(d[key]):    
                if d[key][0]:        
                    total += count[key][right+1]
                temp += v
                while temp > k:
                    temp -= d[key][left]
                    total -= count[key][left]
                    left += 1
                ans = max(ans, total)
        return ans